package code;

import java.util.LinkedList;
import java.util.Queue;


/**
 * @author Clover
 *
 */
public class NumberOfIslands {
	
	/*
	 * bfsֱ����
	 */
	
	public void bfs(char[][] grid,int x,int y,boolean[][] vis,int n,int m){
		int[][] dir={{0,1},{0,-1},{1,0},{-1,0}};
		Queue<Integer> queue=new LinkedList<Integer>();
		queue.add(x*m+y);
		vis[x][y]=true;
		while(!queue.isEmpty()){
			int head=queue.poll();
			int hx=head/m;
			int hy=head%m;
			for(int i=0;i<4;i++){
				int tx=hx+dir[i][0];
				int ty=hy+dir[i][1];
				if(tx>=0 && tx<n && ty>=0 && ty<m && !vis[tx][ty] && grid[tx][ty]=='1'){
					queue.add(tx*m+ty);
					vis[tx][ty]=true;
				}
			}
		}
	}
	public int numIslands(char[][] grid){
		int i,j;
		int n=grid.length;
		if(n==0)	return 0;
		int m=grid[0].length;
		boolean[][] vis=new boolean[n][m];
		int cnt=0;
		for(i=0;i<n;i++){
			for(j=0;j<m;j++){
				if(grid[i][j]=='1' && !vis[i][j]){
					bfs(grid,i,j,vis,n,m);
					cnt++;
				}
			}
		}
		System.out.println(cnt);
		return cnt;
	}
	public static void main(String[] args){
		NumberOfIslands no=new NumberOfIslands();
		char[][] grid={{'1','1','0','0','0'},
				{'1','1',0,'0','0'},
				{'0','0','1','0','0'},
				{'0','0','0','1','1'}};
		no.numIslands(grid);
	}
}
